#include <iostream>
#include <algorithm>

struct Node {
    Node *left;
    Node *right;
};

struct RESULT {
    int distance;
    int depth;
};



RESULT find_max_len(Node *root)
{
    if (root == NULL) {
        RESULT rs = {0, -1};
        return rs;
    }

    RESULT lf = find_max_len(root->left);
    RESULT rt = find_max_len(root->right);
    RESULT rs;
    rs.distance = std::max(std::max(lf.distance, rt.distance), lf.depth + rt.depth + 2);
    rs.depth = std::max(lf.depth + 1, rt.depth + 1);
    return rs;
}

void link(Node *nodes, int parent, int left, int right)
{
    if (left != -1) {
        nodes[parent].left = &nodes[left];
    }

    if (right != -1) {
        nodes[parent].right = &nodes[right];
    }
}

int main(int argc, const char *argv[])
{
    //P241 Graph 3-12
    Node test1[9] = {};
    link(test1, 0, 1, 2);
    link(test1, 1, 3, 4);
    link(test1, 2, 5, 6);
    link(test1, 3, 7, -1);
    link(test1, 5, -1, 8);
    std::cout << find_max_len(test1).distance << std::endl;

    //P242 3-13 left
    Node test2[4] = {};
    link(test2, 0, 1, 2);
    link(test2, 1, 3, -1);
    std::cout << find_max_len(test2).distance << std::endl;

    //P242 3-13 right
    Node test3[9] = {};
    link(test3, 0, -1, 1);
    link(test3, 1, 2, 3);
    link(test3, 2, 4, -1);
    link(test3, 3, 5, 6);
    link(test3, 4, 7, -1);
    link(test3, 5, -1, 8);
    std::cout << find_max_len(test3).distance << std::endl;

    //P242 3-14
    Node test4[9] = {};
    link(test4, 0, 1, 2);
    link(test4, 1, 3, 4);
    link(test4, 2, 5, 6);
    link(test4, 3, 7, -1);
    link(test4, 5, -1, 8);
    std::cout << find_max_len(test4).distance << std::endl;

    //P243 3-15
    Node test5[9] = {};
    link(test5, 0, 1, 2);
    link(test5, 1, 3, 4);
    link(test5, 3, 5, 6);
    link(test5, 5, 7, -1);
    link(test5, 6, -1, 8);
    std::cout << find_max_len(test5).distance << std::endl;

    return 0;
}
